The present invention concerns the optimal placement of components of a very large scale integrated (VLSI) circuit.
In the design of VLSI circuits, circuitry consists of functional blocks of logic, often called components, which are interconnected by networks of connection lines. In order to most efficiently use space on a VLSI circuit, it is desirable to place components on the VLSI circuit so as to minimize a cost metric, for example, the total length of all connection lines between the components. In order to do this, in general, it is desirable to place components which are attached to the same connection line network in close proximity with one another. However, since the number of components is generally very large and the interconnections between components are exceedingly complex, an optimal placement of components can be difficult to find.
One method in the prior art is to make an initial placement of the components and then use a greedy algorithm to improve the initial placement. The initial placement may be done, for example, using a mincut algorithm such as that described in C. M. Fiduccia and R. M. Mattheyses, A Linear-Time Heuristic for Improving Network Partitions, Proceedings of the 19th Design Automation Conference, 1982, pp. 241-247. Once an initial placement is made, the greedy algorithm will check whether the cost metric is decreased by exchanging the location of various components. When the algorithm determines that the exchange does in fact lead to such a cost reduction, the exchange is made. The greedy algorithm is completed when exchanges no longer lead to a decrease in the cost metric.
One drawback to the use of a greedy algorithm is that the algorithm may find a local minimum in the cost metric, but not find the global minimum in the cost metric and thus the optimal placement of components. One attempt to overcome this shortcoming of greedy algorithms is to apply the greedy algorithm to a number of randomly selected initial placements. Using such a "multiple start" greedy algorithm, several local minima of the cost metric may be obtained which increase the chance the global minimum will be discovered. See for example, J. B. Lasserre, P. P. Varaiya, J. Walrand, Simulated Annealing, Random Search, MultiStart or SAD?, Systems and Control Letters 8 (1987) 297-301.
Alternately, other types of algorithms may be used. For example, a simulated annealing algorithm may be used which will, in the process of searching for a global minimum, allow for the exchange of location of various components which result in an increase in the cost metric. See for example, S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing, Science, vol. 220, no. 4598, pp. 671-680, May 13, 1983. In effect the simulated annealing algorithms apply sufficient brute force to adequately sample the entire range of component placement configurations, and then very gradually narrow the search to a component placement arrangement which has a local "valley" with a low global cost metric.
The primary drawback of using placement schemes such as multiple start greedy algorithms or Simulated Annealing algorithms is that they require significant computer resources to perform. It is desirable, therefore to develop other algorithms which are able to generate a component placement with a global minimum cost metric which will not require so significant an amount of computer run time.